{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Backspace String Compare"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #two-pointers #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #双指针 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: backspaceCompare"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #比较含退格的字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定 <code>s</code> 和 <code>t</code> 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 <code>true</code> 。<code>#</code> 代表退格字符。</p>\n",
    "\n",
    "<p><strong>注意：</strong>如果对空文本输入退格字符，文本继续为空。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ab#c\", t = \"ad#c\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>s 和 t 都会变成 \"ac\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ab##\", t = \"c#d#\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>s 和 t 都会变成 \"\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a#c\", t = \"b\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>s 会变成 \"c\"，但 t 仍然是 \"b\"。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, t.length &lt;= 200</code></li>\n",
    "\t<li><code>s</code> 和 <code>t</code> 只含有小写字母以及字符 <code>'#'</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以用 <code>O(n)</code> 的时间复杂度和 <code>O(1)</code> 的空间复杂度解决该问题吗？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [backspace-string-compare](https://leetcode.cn/problems/backspace-string-compare/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [backspace-string-compare](https://leetcode.cn/problems/backspace-string-compare/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ab#c\"\\n\"ad#c\"', '\"ab##\"\\n\"c#d#\"', '\"a#c\"\\n\"b\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S,T):\n",
    "        def bui(S):\n",
    "            ans=[]\n",
    "            for i in S:\n",
    "                if i !='#':\n",
    "                    ans.append(i)\n",
    "                elif ans:\n",
    "                    ans.pop()\n",
    "            return \"\".join(ans)\n",
    "        return bui(S)==bui(T)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S, T):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type T: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        txt_s = []\n",
    "        txt_t = []\n",
    "        self.generate_txt(S, txt_s)\n",
    "        self.generate_txt(T, txt_t)\n",
    "\n",
    "        diff = (txt_s == txt_t)\n",
    "        return diff\n",
    "    \n",
    "    def generate_txt(self, string, txt):\n",
    "        for val in string:\n",
    "            length = len(txt)\n",
    "            if val == '#' and length != 0:\n",
    "                txt.pop(-1)\n",
    "            elif val == '#' and length == 0:\n",
    "                pass\n",
    "            else:\n",
    "                txt.append(val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def backspaceCompare(self, S, T):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type T: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        s = len(S) - 1\n",
    "        t = len(T) - 1\n",
    "        while s>=0 or t>=0:\n",
    "            char1, char2 = \"\", \"\"\n",
    "            if s>=0: char1, s = self.getChar(S, s)\n",
    "            if t>=0: char2, t = self.getChar(T, t)\n",
    "            if char1!=char2: return False\n",
    "        return True\n",
    "            \n",
    "    def getChar(self, S, r):\n",
    "        char, count = \"\", 0\n",
    "        while not char and r >= 0:\n",
    "            if S[r]==\"#\":\n",
    "                count+=1\n",
    "            elif count==0:\n",
    "                char = S[r]\n",
    "            else:\n",
    "                count-=1\n",
    "            r-=1\n",
    "        return char, r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S, T):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type T: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def back(s):\n",
    "            l,temp=list(s),[]\n",
    "            for i in l:\n",
    "                if i!=\"#\":\n",
    "                    temp.append(i)\n",
    "                else:\n",
    "                    if temp:\n",
    "                        temp.pop()\n",
    "            return temp\n",
    "        \n",
    "        return back(S)==back(T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        return self.compare(S) == self.compare(T)\n",
    "        \n",
    "    \n",
    "    def compare(self, Str: str) -> list:\n",
    "        l = []\n",
    "        for s in Str:\n",
    "            if s == \"#\":\n",
    "                if l != []:\n",
    "                    l.pop()\n",
    "            else:\n",
    "                l.append(s)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dobackspace(self,string):\n",
    "        stack = ''\n",
    "        length = len(string)\n",
    "        for i in range(length):\n",
    "            if string[i] == '#':\n",
    "                len1 = len(stack)\n",
    "                if len1 != 0:\n",
    "                    stack = stack[:len1-1]\n",
    "                else:\n",
    "                    pass\n",
    "            else:\n",
    "                stack += string[i]\n",
    "        print(stack)\n",
    "        return stack\n",
    "    def backspaceCompare(self, S, T):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type T: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if self.dobackspace(S) == self.dobackspace(T):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S, T):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :type T: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def escapeBack(string):\n",
    "            stack = []\n",
    "            for s in string:\n",
    "                if stack and s == '#':\n",
    "                    stack.pop()\n",
    "                elif s != '#':\n",
    "                    stack.append(s)\n",
    "                    \n",
    "            return stack\n",
    "        \n",
    "        return (escapeBack(S) == escapeBack(T))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: 'str', T: 'str') -> 'bool':\n",
    "        S1 = []\n",
    "        for i, c in enumerate(S):\n",
    "            if c == '#':\n",
    "                if S1:\n",
    "                    S1.pop()\n",
    "            else:\n",
    "                S1.append(c)\n",
    "        T1 = []\n",
    "        for i, c in enumerate(T):\n",
    "            if c == '#':\n",
    "                if T1:\n",
    "                    T1.pop()\n",
    "            else:\n",
    "                T1.append(c)\n",
    "        return S1 == T1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        st1=[]\n",
    "        st2=[]\n",
    "        for x in S:\n",
    "            if x=='#':\n",
    "                if len(st1)>0:\n",
    "                    st1.pop()\n",
    "            else:\n",
    "                st1.append(x)\n",
    "        for x in T:\n",
    "            if x=='#':\n",
    "                if len(st2)>0:\n",
    "                    st2.pop()\n",
    "            else:\n",
    "                st2.append(x)\n",
    "        if st1==st2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        for i in S:\n",
    "            if i == '#':\n",
    "                if stack1 == []:\n",
    "                    pass\n",
    "                else:\n",
    "                    stack1.pop()\n",
    "            else:\n",
    "                stack1.append(i)\n",
    "        for j in T:\n",
    "            if j == '#':\n",
    "                if stack2 == []:\n",
    "                    pass\n",
    "                else:\n",
    "                    stack2.pop()\n",
    "            else:\n",
    "                stack2.append(j)\n",
    "        return stack1 == stack2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        stack_S=[]\n",
    "        stack_T=[]\n",
    "        for i in S:\n",
    "            if i==\"#\" and stack_S!=[]:\n",
    "                stack_S.pop()\n",
    "            elif i==\"#\"and stack_S==[]:\n",
    "                continue\n",
    "            else:stack_S.append(i)\n",
    "        for i in T:\n",
    "            if i == \"#\" and stack_T!=[]:\n",
    "                stack_T.pop()\n",
    "            elif i == \"#\" and stack_T == []:\n",
    "                continue\n",
    "            else:\n",
    "                stack_T.append(i)\n",
    "        return stack_S==stack_T\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        l1 = []\n",
    "        l2 = []\n",
    "        for i in S:\n",
    "            if i == '#':\n",
    "                if l1:\n",
    "                    l1.pop()\n",
    "                continue\n",
    "            l1.append(i)\n",
    "        for i in T:\n",
    "            if i == '#':\n",
    "                if l2:\n",
    "                    l2.pop()\n",
    "                continue\n",
    "            l2.append(i)\n",
    "\n",
    "        return l1==l2\n",
    "                  \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        def build(S: str) -> str:\n",
    "            news = list()\n",
    "            for i in S:\n",
    "                if i != '#':\n",
    "                    news.append(i)\n",
    "                elif news:\n",
    "                    news.pop()\n",
    "            return \"\".join(news)\n",
    "        \n",
    "        return build(S) == build(T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        stack1,stack2 = [],[]\n",
    "\n",
    "        for i in S:\n",
    "            if i !='#':\n",
    "                stack1.append(i)\n",
    "            else:\n",
    "                if len(stack1)>0:\n",
    "                    stack1.pop()\n",
    "                \n",
    "\n",
    "        for i in T:\n",
    "            if i !='#':\n",
    "                stack2.append(i)\n",
    "            else:\n",
    "                if len(stack2)>0:\n",
    "                    stack2.pop()\n",
    "        if stack1 == stack2:\n",
    "            return True\n",
    "        else:\n",
    "            return False              \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        tmp_s = self.tmp_str(S)\n",
    "        tmp_t = self.tmp_str(T)\n",
    "        return tmp_s == tmp_t\n",
    "\n",
    "    def tmp_str(self, tmp_str):\n",
    "        tmp_s = []\n",
    "        for i in range(len(tmp_str)):\n",
    "            if tmp_str[i] != \"#\":\n",
    "                tmp_s.append(tmp_str[i])\n",
    "            # else:\n",
    "            #     tmp_s = tmp_s[:-1]\n",
    "            elif tmp_s:\n",
    "                tmp_s.pop()\n",
    "        return tmp_s\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    print(Solution().backspaceCompare(\"a#c\", \"b\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        \"\"\"\n",
    "        用栈来保存字符，遇到#就删除栈顶元素\n",
    "        \"\"\"\n",
    "        stringS = self.deleteSpaceBar(S)\n",
    "        stringT = self.deleteSpaceBar(T)\n",
    "\n",
    "        return True if stringS == stringT else False\n",
    "        \n",
    "    \n",
    "    def deleteSpaceBar(self, string):\n",
    "        \"\"\"\n",
    "        用栈来保存字符，遇到#就删除栈顶元素\n",
    "        \"\"\"\n",
    "        stringChars = []\n",
    "        for char in string:\n",
    "            if char == \"#\" and stringChars:\n",
    "                stringChars.pop()\n",
    "            else:\n",
    "                stringChars.append(char)\n",
    "        # 串接\n",
    "        stringChars = \"\".join(stringChars).replace(\"#\", \"\")\n",
    "        \n",
    "        return stringChars"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        # def builds(s):\n",
    "        #     stack = []\n",
    "        #     for i in s:\n",
    "        #         if i!='#':\n",
    "        #             stack.append(i)\n",
    "        #         elif stack:\n",
    "        #             stack.pop()    \n",
    "        #     return ''.join(stack)\n",
    "\n",
    "        # return builds(S)==builds(T)\n",
    "        i,j = len(S)-1,len(T)-1\n",
    "        skipS = skipT = 0\n",
    "        while i>=0 or j>=0:\n",
    "            while i>=0:\n",
    "                print(i)\n",
    "                if S[i]=='#':\n",
    "                    skipS+=1\n",
    "                    i-=1\n",
    "                elif skipS>0:\n",
    "                    skipS-=1\n",
    "                    i-=1\n",
    "                else:\n",
    "                    break\n",
    "            while j>=0:\n",
    "                if T[j] == '#':\n",
    "                    skipT += 1\n",
    "                    j -= 1\n",
    "                elif skipT > 0:\n",
    "                    skipT -= 1\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    break\n",
    "            if i>=0 and j>=0:\n",
    "                if S[i]!=T[j]:\n",
    "                    return False\n",
    "            elif i>=0 or j>=0:\n",
    "                return False\n",
    "            i-=1\n",
    "            j-=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, S: str, T: str) -> bool:\n",
    "        a = []\n",
    "        b = []\n",
    "        for i in range(len(S)):\n",
    "            if S[i] != '#':\n",
    "                a.append(S[i])\n",
    "            elif S[i] == '#' and a != []:\n",
    "                a.pop()\n",
    "        for i in range(len(T)):\n",
    "            if T[i] !='#':\n",
    "                b.append(T[i])\n",
    "            elif T[i] == '#' and b !=[]:\n",
    "                b.pop()\n",
    "        return a == b     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, s: str, t: str) -> bool:\n",
    "        def BuildStr(s: str) -> str:\n",
    "            ret = []\n",
    "            for ch in s:\n",
    "                if ch != '#':\n",
    "                    ret.append(ch)\n",
    "                elif ret:\n",
    "                    ret.pop()\n",
    "            return ''.join(ret)\n",
    "        return BuildStr(s) == BuildStr(t)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, s: str, t: str) -> bool:\n",
    "\n",
    "        # 法1：用栈处理遍历过程，每次遍历到一个字符：\n",
    "        # 如果它是退格符，那么我们将栈顶弹出；\n",
    "        # 如果它是普通字符，那么我们将其压入栈中。\n",
    "        def build(s):\n",
    "            ret = []\n",
    "            for ch in s:\n",
    "                if ch=='#':\n",
    "                    if ret!=[]:   # ret非空才可以pop，否则报错\n",
    "                        ret.pop()\n",
    "                else:  \n",
    "                    ret.append(ch)\n",
    "            return ''.join(ret)\n",
    "\n",
    "        return build(s)==build(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, s: str, t: str) -> bool:\n",
    "        # 定义栈\n",
    "        stack1, stack2 = [], []\n",
    "        # 遍历字符串\n",
    "        for c in s:\n",
    "            # 如果当前字符不是 #，将当前字符入栈\n",
    "            if c != \"#\":\n",
    "                stack1.append(c)\n",
    "            # 如果当前字符是 #，将栈顶元素出栈\n",
    "            elif stack1:\n",
    "                stack1.pop()\n",
    "        # 遍历字符串\n",
    "        for c in t:\n",
    "            # 如果当前字符不是 #，将当前字符入栈\n",
    "            if c != \"#\":\n",
    "                stack2.append(c)\n",
    "            # 如果当前字符是 #，将栈顶元素出栈\n",
    "            elif stack2:\n",
    "                stack2.pop()\n",
    "        # 将栈中的元素组合成字符串\n",
    "        return \"\".join(stack1) == \"\".join(stack2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, s: str, t: str) -> bool:\n",
    "        s1=0\n",
    "        f=0\n",
    "        s=list(s)\n",
    "        t=list(t)\n",
    "        print(s)\n",
    "        while f<len(s):\n",
    "            if s[f]=='#':\n",
    "                f+=1\n",
    "                if s1-1<0:\n",
    "                    s1=s1\n",
    "                else:\n",
    "                    s1-=1\n",
    "            else:\n",
    "                s[s1]=s[f]\n",
    "                print(s1)\n",
    "                s1+=1\n",
    "                f+=1\n",
    "        print(s[:s1])\n",
    "        s2=0\n",
    "        f2=0\n",
    "        while f2<len(t):\n",
    "            if t[f2]=='#':\n",
    "                f2+=1\n",
    "                if s2-1<0:\n",
    "                    s2=s2\n",
    "                else:\n",
    "                    s2-=1\n",
    "            else:\n",
    "                t[s2]=t[f2]\n",
    "                s2+=1\n",
    "                f2+=1\n",
    "        print(t[:s2])\n",
    "        if t[:s2]==s[:s1]: return True\n",
    "        else: return False\n",
    "        \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def relu(num):\n",
    "    if num > 0 :\n",
    "        return num\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "def calstep( str:str , pos ):\n",
    "    step = 0\n",
    "    while step < 2 * str.count('#', relu(pos - step) , pos + 1) :\n",
    "        step = step + 1\n",
    "    return step \n",
    " \n",
    "class Solution:\n",
    "    def backspaceCompare(self, s: str, t: str) -> bool:\n",
    "        sp , tp = len(s) - 1 , len(t) - 1   #定义遍历对照的指针\n",
    "        ss , ts = 0 , 0                     #定义需要跳过的步长\n",
    "        while sp >= 0 or tp >= 0:                     #以s为参照，遍历查询t\n",
    "            if(sp >= 0 ):\n",
    "                ss = (calstep( s , sp ) ) // 2 + ss               #求移动步长\n",
    "                sp = sp - calstep( s , sp )           #移动后指针位置\n",
    "            if(tp >= 0):\n",
    "                ts = (calstep( t , tp ) ) // 2 + ts\n",
    "                tp = tp - calstep( t , tp )\n",
    "            print(ss,sp,ts,tp)\n",
    "            if( tp <= 0 and sp <= 0 and tp != sp):\n",
    "                break\n",
    "            if ts == ss :\n",
    "                if t[tp] != '#':\n",
    "                    tp = tp - 1\n",
    "                else:\n",
    "                    continue\n",
    "                if s[sp] != '#':\n",
    "                    sp = sp - 1\n",
    "                else:\n",
    "                    continue\n",
    "                ss = 0\n",
    "                ts = 0\n",
    "                if s[sp] == t[tp] or (sp < 0 and tp < 0) or s[sp] == '#' or t[tp] == '#':\n",
    "                    continue\n",
    "                else:\n",
    "                    print(tp,sp)\n",
    "                    print(ts,ss)\n",
    "                    print(1)\n",
    "                    return False\n",
    "            elif ts > ss:\n",
    "                if s[sp] != '#':\n",
    "                    if s[sp] == t[tp] or s[sp] == '#' or t[tp] == '#':\n",
    "                        ts = 0\n",
    "                        if t[tp] != '#':\n",
    "                            tp = tp - 1\n",
    "                        else:\n",
    "                            continue\n",
    "                    else:\n",
    "                        print(tp,sp)\n",
    "                        print(ts,ss)\n",
    "                        print(2)\n",
    "                        if sp < 0 and tp < 0 and ts != ss and sp != tp:\n",
    "                            return True\n",
    "                        return False\n",
    "                    sp = sp - 1\n",
    "            else:\n",
    "                if t[tp] != '#':\n",
    "                    if s[sp] == t[tp] or s[sp] == '#' or t[tp] == '#':\n",
    "                        ss = 0\n",
    "                        if s[sp] != '#':\n",
    "                            sp = sp - 1\n",
    "                        else:\n",
    "                            continue\n",
    "                    else:\n",
    "                        print(tp,sp)\n",
    "                        print(ts,ss)\n",
    "                        print(3)\n",
    "                        if sp < 0 and tp < 0 and ts != ss and sp != tp:\n",
    "                            return True\n",
    "                        return False\n",
    "                    tp = tp - 1\n",
    "        if sp == tp :\n",
    "            print(tp,sp)\n",
    "            print(ts,ss)\n",
    "            print(4)\n",
    "            return True\n",
    "        elif (sp < -1 or tp < -1) and sp != 0 and tp != 0:\n",
    "            print(tp,sp)\n",
    "            print(ts,ss)\n",
    "            print(5)\n",
    "            return True\n",
    "        else:\n",
    "            print(tp,sp)\n",
    "            print(ts,ss)\n",
    "            print(6)\n",
    "            return False\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, s: str, t: str) -> bool:\n",
    "        a = []\n",
    "        b = []\n",
    "        for i in range(len(s)):\n",
    "            a.append(s[i])\n",
    "        for i in range(len(t)):\n",
    "            b.append(t[i])\n",
    "        i = 0\n",
    "        while True:\n",
    "            if i > len(a)-1:\n",
    "                break\n",
    "            if a[i] == \"#\":\n",
    "                del a[i]\n",
    "                if i != 0:\n",
    "                    del a[i-1]\n",
    "                i = 0\n",
    "                continue\n",
    "            i += 1\n",
    "        i = 0\n",
    "        while True:\n",
    "            if i > len(b)-1:\n",
    "                break\n",
    "            if b[i] == \"#\":\n",
    "                del b[i]\n",
    "                if i != 0:\n",
    "                    del b[i-1]\n",
    "                i = 0\n",
    "                continue\n",
    "            i += 1\n",
    "        if a == b:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, s: str, t: str) -> bool:\n",
    "        def get_str(chr):\n",
    "            res = []\n",
    "            for i in range(len(chr)):\n",
    "                if chr[i] != '#':\n",
    "                    res.append(chr[i])\n",
    "                else:\n",
    "                    if res:\n",
    "                        res.pop()\n",
    "            return ''.join(res)\n",
    "        \n",
    "        res_s, res_t = get_str(s), get_str(t)\n",
    "        return res_s == res_t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backspaceCompare(self, s: str, t: str) -> bool:\n",
    "        s1 = []\n",
    "        t1 = []\n",
    "        for x in s:\n",
    "            if x == \"#\":\n",
    "                if s1:\n",
    "                    s1.pop()\n",
    "                continue\n",
    "            s1.append(x)\n",
    "        for y in t:\n",
    "            if y == \"#\":\n",
    "                if t1:\n",
    "                    t1.pop()\n",
    "                continue\n",
    "            t1.append(y)\n",
    "        print(s1)\n",
    "        print(t1)\n",
    "        return s1 == t1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
